// fhq - treap 简易模板
#include <bits/stdc++.h>
#define ls(p) t[p].l
#define rs(p) t[p].r
#define mid ((l+r)>>1)
using namespace std;
const int N = 100010;
mt19937 rd(random_device{}()); // random maker
struct node {
    int l,r,siz,rnd,val,tag; /* other data/tags */
}t[N]; int tot,root;
/* ---------- for recycle nodes ------------
int cyc[N],cyccnt;
inline void delnode(int p) {cyc[++cyccnt]=p;}
inline void newnode(int val) {
    int id=(cyccnt>0)?cyc[cyccnt--]:++tot;
    t[id]={0,0,1,(int)(rd()),val}; return id;
}
*/
inline int newnode(int val) { t[++tot]={0,0,1,(int)(rd()),val}; return tot;} // create a new node
inline void updata(int p) {t[p].siz=t[ls(p)].siz+t[rs(p)].siz+1; /* pushup other datas */ }
inline void pushtag(int p,int vl) { /* tag to push */ }
inline void pushdown(int p) {
    if(t[p].tag!=std_tag) {
        if(ls(p)) pushtag(ls(p),t[p].tag);
        if(rs(p)) pushtag(rs(p),t[p].tag);
        t[p].tag=std_tag;
    }
}
int merge(int p,int q) { 
    if(!p||!q) return p+q;
    if(t[p].rnd<t[q].rnd) {
        pushdown(p);
        rs(p)=merge(rs(p),q);
        updata(p); return p;
    }else {
        pushdown(q);
        ls(q)=merge(p,ls(q));
        updata(q); return q;
    }
}
void split(int p,int k,int &x,int &y) { 
    if(!p) x=0,y=0;
    else {
        pushdown(p);
        if(t[ls(p)].siz>=k) y=p,split(ls(p),k,x,ls(p));
        else x=p,split(rs(p),k-t[ls(p)].siz-1,rs(p),y);
        updata(p);
    }
}
int build(int l,int r) { // build tree on a[l..r], return the root 
    if(l>r) return 0;
    return merge(build(l,mid-1),merge(newnode(a[mid]),build(mid+1,r)));
}
/*
    other functions base on split() and merge()
    
*/
int main() {

}